import java.util.Arrays;

public class SelectionSort {

    private SelectionSort() {
    }

    // 使用额外空间进行排序
    public static <E extends Comparable<E>> E[] sortWithCap(E[] data) {
        if (data == null || data.length <= 1) {
            return data;
        }

        E[] temp = data.clone();
        // TODO 使用额外空间进行选择排序

        return temp;
    }

    // 原地选择排序 
    public static <E extends Comparable<E>> void sort(E[] data) {
        if (data == null || data.length <= 1 ) {
            return;
        }

        for (int i = 0; i < data.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < data.length; j++) {
                // 元素值是可以比较的, 基于比较的排序算法
                if (data[j].compareTo(data[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            SortingHelper.swap(data, i, minIndex);
        }

    }

    public static <E extends Comparable<E>> void sortReverse(E[] data) {
        if (data == null || data.length <= 1) return;
        for (int i = data.length - 1; i >= 0; i--) {
            int maxIndex = i;
            for (int j = i - 1; j >= 0; j--)
                if (data[j].compareTo(data[maxIndex]) > 0)
                    maxIndex = j;
            SortingHelper.swap(data, i, maxIndex);
        }
    }


}
